#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 2e4+10;
const int M = 1e4+10;

int n,m,h1[N],h2[N],cnt,k[N];
bool vis[N],v[N];
vector<int> p[N];
struct edge{int v,nxt;}e[M<<1];
void link1(int x,int y){e[++cnt] = (edge){y,h1[x]};h1[x] = cnt;}
void link2(int x,int y){e[++cnt] = (edge){y,h2[x]};h2[x] = cnt;}

int dfs(int x){
	if(vis[x]) return k[x];
	vis[x] = 1;
	for(int i = h1[x];i;i = e[i].nxt){
		int y = e[i].v;
	    int tt = dfs(y);
		if(k[x] > tt-1) k[x] = tt-1;
	}
	p[k[x]].pb(x); 
	return k[x];
}

void rdfs(int x){
	if(v[x]) return; v[x] = 1; 
	for(int i = h2[x];i;i = e[i].nxt){
		int y = e[i].v;
		rdfs(y);
	}
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in;
	for(int i = 1;i <= n;i++) k[i] = in;
	for(int i = 1;i <= m;i++){
		int x = in,y = in;
		link1(x,y); link2(y,x);
	}
	for(int i = 1;i <= n;i++) dfs(i);
	for(int i = 1;i <= n;i++)
		for(int j = 0;j < p[i].size();j++)
			printf("%d ",p[i][j]);
	puts("");
	for(int i = 1;i <= n;i++){
		memset(v,0,sizeof(v)); rdfs(i);
		int tot = 0;
		for(int x = n;x;x--){
			if(tot < n - x) break;
			for(int j = 0;j < p[x].size();j++)
				if(!v[p[x][j]]) tot++,v[p[x][j]] = 1;
		}
		printf("%d ",n-tot);
	}puts("");
	return 0;
}

